package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/swap-nodes-in-pairs/"> 两两交换链表中的节点(Swap Nodes in Pairs)</a>
 * <p>给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *          1 -> 2 -> 3 -> 4
 *      ==> 2 -> 1 -> 4 -> 3
 *      输入：head = [1,2,3,4]
 *      输出：[2,1,4,3]
 *
 * 示例 2：
 *      输入：head = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：head = [1]
 *      输出：[1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点的数目在范围 [0, 100] 内</li>
 *     <li>0 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/4/27 9:18
 */
public class LC0024SwapNodesInPairs_M {
    static class Solution {
        public ListNode swapPairs(ListNode head) {
            //return swapPairsByIterator(head);
            return swapPairsByRecursion(head);

        }

        private ListNode swapPairsByIterator(ListNode head) {
            // 虚拟头节点
            ListNode dummyNode = new ListNode(-1, head);
            ListNode currNode = dummyNode;
            while (currNode.next != null && currNode.next.next != null) {
                ListNode next1 = currNode.next;
                ListNode next2 = currNode.next.next;
                ListNode next3 = currNode.next.next.next;
                currNode.next = next2;
                next2.next = next1;
                next1.next = next3;
                currNode = currNode.next.next;
            }
            return dummyNode.next;
        }

        private ListNode swapPairsByRecursion(ListNode curr) {
            // 空节点或者单个节点无需交换
            if (curr == null || curr.next == null) {
                return curr;
            }
            ListNode nextNext = swapPairsByRecursion(curr.next.next);
            ListNode next = curr.next;
            next.next = curr;
            curr.next = nextNext;
            return next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        Solution solution = new Solution();
        // 2 -> 1 -> 3 -> 4 -> null
        Printer.printListNode(solution.swapPairs(head));
    }
}
